This is a Phase I/IIa study of a 24-hour infusion of gemcitabine in combination with cisplatin and dexamethasone. Treatment cycles are repeated every three weeks until a maximum response is achieved. Doses of gemcitabine will be escalated in cohorts of three or more patients. Dose escalation of gemcitabine will be performed until the MTD is defined. Pretreated patients with recurrent (low, intermediate grades and selected high grade) NHL will be considered for this study. In the Phase IIa component of this study, once the MTD of gemcitabine has been reached, an additional group of patients will be treated at one dose below the MTD. This approach will give an early view of efficacy and will expand our knowledge of the toxicity profile of this regimen.